home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / src / plane / _polygon.bak < prev    next >
Encoding:
Text File  |  1991-11-15  |  8.0 KB  |  399 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _polygon.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/plane.h>
  17. #include <math.h>
  18.  
  19. #ifndef __TURBOC__
  20. #include <LEDA/plane_alg.h>
  21. declare(edge_array,bool)
  22. #endif
  23.  
  24.  
  25. //------------------------------------------------------------------------------
  26. // polygons
  27. //------------------------------------------------------------------------------
  28.  
  29.  
  30. polygon_rep::polygon_rep(list(segment) L) 
  31. { 
  32.   seg_list = L;
  33.   count = 1; 
  34.  }
  35.  
  36. polygon_rep::polygon_rep()         { count = 1; }
  37.  
  38. polygon::polygon()                 { ptr = new polygon_rep; }
  39. polygon::polygon(int)              { ptr = new polygon_rep; }
  40. polygon::polygon(polygon& P)       { ptr = P.ptr; ptr->count++; }
  41. polygon::polygon(ent x)            { ptr=(polygon_rep*)x; ptr->count++; }
  42. void polygon::clear()              { if (--(ptr->count)==0) delete ptr; }
  43.  
  44.  
  45. ostream& operator<<(ostream& out, const polygon& p) 
  46. { p.vertices().print();
  47.   return out;
  48.  } 
  49.  
  50. istream& operator>>(istream& in,  polygon& p) 
  51. { list(point) L; 
  52.   L.read(); 
  53.   p = polygon(L); 
  54.   return in;
  55. }
  56.  
  57.  
  58. void polygon_check(list(segment)&);
  59.  
  60. polygon::polygon(list(point)& pl, bool check)
  61. { ptr = new polygon_rep;
  62.  
  63.   list_item it,it1;
  64.  
  65.   forall_list_items(it,pl)
  66.   { it1 = pl.cyclic_succ(it);
  67.     ptr->seg_list.append(segment(pl[it],pl[it1]));
  68.    }
  69.  
  70.   if (check) polygon_check(ptr->seg_list);
  71. }
  72.  
  73. list(point) polygon::vertices() const
  74. { list(point) result;
  75.   segment s;
  76.   forall(s,ptr->seg_list) result.append(s.start());
  77.   return result;
  78. }
  79.  
  80.  
  81.  
  82.  
  83. void polygon_check(list(segment)& seg_list)
  84. {  if (seg_list.length() < 3) 
  85.      error_handler(1,"polygon: must be simple");
  86.  
  87. #ifndef __TURBOC__
  88.    list(point) L;
  89.    SWEEP_SEGMENTS(seg_list,L);
  90.  
  91.   if (L.length() != seg_list.length())
  92.    error_handler(1,"polygon: must be simple");
  93. #endif
  94.  
  95.   list_item it;
  96.  
  97.   double angle = 0;
  98.  
  99.   forall_list_items(it,seg_list)
  100.   { list_item succ = seg_list.cyclic_succ(it);
  101.     segment s1 = seg_list[it];
  102.     segment s2 = seg_list[succ];
  103.     angle += s1.angle(s2);
  104.    }
  105.  
  106.   if (angle > 0)
  107.    error_handler(1,"polygon: point list must be clockwise oriented.");
  108. }
  109.  
  110. polygon polygon::translate(double alpha, double d)
  111. { list(point) L;
  112.   segment s;
  113.   forall(s,ptr->seg_list) L.append(s.start().translate(alpha,d));
  114.   return polygon(L,false);
  115. }
  116.  
  117. polygon polygon::translate(const vector& v)
  118. { list(point) L;
  119.   segment s;
  120.   forall(s,ptr->seg_list) L.append(s.start().translate(v));
  121.   return polygon(L,false);
  122. }
  123.  
  124. polygon polygon::rotate(point origin, double alpha)
  125. { list(point) L;
  126.   segment s;
  127.   forall(s,ptr->seg_list) L.append(s.start().rotate(origin,alpha));
  128.   return polygon(L,false);
  129. }
  130.  
  131. polygon polygon::rotate(double alpha)
  132. { return rotate(point(0,0),alpha);
  133.  }
  134.  
  135.  
  136. /*
  137.  
  138. bool polygon::inside(point p)
  139. {
  140.   line l(p,M_PI_2);  // vertical line through p
  141.  
  142.   int count = 0;
  143.  
  144.   segment s;
  145.   forall(s,ptr->seg_list)
  146.   { point q;
  147.     if (!l.intersection(s,q)) continue;
  148.     if (q.ycoord() < p.ycoord()) continue;
  149.     if (q == s.start())  continue;
  150.     if (q == s.end())  continue;
  151.     count++ ;
  152.    }
  153.  
  154.   list(point) plist = vertices();
  155.  
  156.   list_item i = plist.first();;
  157.  
  158.   forall_items(i,plist)
  159.   { 
  160.     point q = plist[i];
  161.  
  162.     if (q==p) return true;
  163.  
  164.     if (q.xcoord() == p.xcoord() && q.ycoord() > p.ycoord())
  165.     { list_item i0 = plist.cyclic_pred(i);
  166.       list_item i1 = plist.cyclic_succ(i);
  167.       point q0 = plist[i0];
  168.       point q1 = plist[i1];
  169.  
  170.       if (q0.xcoord() < p.xcoord() && q1.xcoord() > p.xcoord()) count++;
  171.       if (q0.xcoord() > p.xcoord() && q1.xcoord() < p.xcoord()) count++;
  172.  
  173.      }
  174.  
  175.    }
  176.  
  177.    return count%2;
  178.  
  179. }
  180.  
  181. */
  182.  
  183.  
  184.  
  185. bool polygon::inside( point p)
  186. {
  187.   line l(p,M_PI_2);  // vertical line through p
  188.  
  189.   int count = 0;
  190.  
  191.   segment s;
  192.   forall(s,ptr->seg_list)
  193.   { point q;
  194.     if (!l.intersection(s,q)) continue;
  195.     if (q.ycoord() < p.ycoord()) continue;
  196.     if (q == s.start())  continue;
  197.     if (q == s.end())  continue;
  198.     count++ ;
  199.    }
  200.  
  201.   list(point) plist = vertices();
  202.  
  203.   list_item i0 = plist.first();
  204.  
  205.   while (plist[i0].xcoord() == p.xcoord())  i0 = plist.cyclic_pred(i0);
  206.  
  207.   list_item i = plist.cyclic_succ(i0);
  208.  
  209.   for(;;)
  210.   { 
  211.     while ( i != i0 && (plist[i].xcoord() != p.xcoord() || 
  212.                         plist[i].ycoord() < p.ycoord()    )  )
  213.        i = plist.cyclic_succ(i);
  214.  
  215.     if (i==i0) break;
  216.  
  217.     point q  = plist[i];
  218.     point q0 = plist[plist.cyclic_pred(i)];
  219.  
  220.     while ((plist[i].xcoord()==p.xcoord()) && (plist[i].ycoord() >= p.ycoord()))
  221.     { if (plist[i]==p) return true;
  222.       i = plist.cyclic_succ(i);
  223.      }
  224.  
  225.     point q1 = plist[i];
  226.  
  227.      if (q0.xcoord() < p.xcoord() && q1.xcoord() > p.xcoord()) count++;
  228.       if (q0.xcoord() > p.xcoord() && q1.xcoord() < p.xcoord()) count++;
  229.  
  230.    }
  231.  
  232.    return count%2;
  233.  
  234. }
  235.  
  236. bool polygon::outside(point p) { return !inside(p); }
  237.  
  238.  
  239. list(point) polygon::intersection(segment s)
  240. { list(point) result;
  241.   segment t;
  242.   point p;
  243.  
  244.   forall(t,ptr->seg_list) 
  245.     if (s.intersection(t,p))
  246.      if (result.empty()) result.append(p);
  247.      else if (p != result.tail() ) result.append(p);
  248.  
  249.   return result;
  250. }
  251.  
  252.  
  253. list(point) polygon::intersection(line l)
  254. { list(point) result;
  255.   segment t;
  256.   point p;
  257.  
  258.   forall(t,ptr->seg_list) 
  259.     if (l.intersection(t,p))
  260.      if (result.empty()) result.append(p);
  261.      else if (p != result.tail() ) result.append(p);
  262.  
  263.   return result;
  264. }
  265.  
  266.  
  267. // intersection with polygon
  268.  
  269. #ifndef __TURBOC__
  270.  
  271. static bool polygon_test_edge(GRAPH(point,int)& G,edge& i1)
  272. { node v = G.target(i1);
  273.  
  274.   edge e,i2=nil,o1=nil,o2=nil;
  275.  
  276.   forall_adj_edges(e,v)
  277.     if (e != i1)
  278.     { if (v==target(e)) i2 = e;
  279.       else if (G[e]== G[i1]) o1 = e;
  280.            else o2 = e;
  281.      }
  282.  
  283.   if (i2==nil) return false;
  284.  
  285.   segment si1(G[source(i1)],G[v]);
  286.   segment si2(G[v],G[source(i2)]);
  287.   segment so2(G[v],G[target(o2)]);
  288.  
  289.   double alpha = si1.angle(si2);
  290.   double beta  = si1.angle(so2);
  291.  
  292.   return (alpha > beta);
  293.  
  294. }
  295.  
  296.  
  297.  
  298. static edge polygon_switch_edge(GRAPH(point,int)& G,edge i1)
  299. { node v = G.target(i1);
  300.  
  301.   edge e,i2=nil,o1=nil,o2=nil;
  302.  
  303.   forall_adj_edges(e,v)
  304.     if (e != i1)
  305.     { if (v==target(e)) i2 = e;
  306.       else if (G[e]== G[i1]) o1 = e;
  307.            else o2 = e;
  308.      }
  309.  
  310.   if (i2==nil) return  o1;
  311.  
  312.   segment si1(G[source(i1)],G[v]);
  313.   segment si2(G[v],G[source(i2)]);
  314.   segment so1(G[v],G[target(o1)]);
  315.   segment so2(G[v],G[target(o2)]);
  316.  
  317.   double alpha = si1.angle(si2);
  318.   double beta  = si1.angle(so2);
  319.   double gamma = si1.angle(so1);
  320.  
  321.   if (alpha < beta) cout << "error: alpa < beta!!\n";
  322.  
  323.   if (gamma >= beta) return o2;
  324.   else return o1;
  325.  
  326. }
  327.  
  328. #endif
  329.  
  330. list(polygon) polygon::intersection(polygon P)
  331. {
  332.  
  333.   list(polygon) result;
  334.  
  335. #ifndef __TURBOC__
  336.  
  337.   GRAPH(point,int) SUB;
  338.  
  339.   SWEEP_SEGMENTS(segments(),P.segments(),SUB);
  340.  
  341.   int N = SUB.number_of_nodes();
  342.  
  343.   if (N < size() + P.size())
  344.    error_handler(1,"polygon: sorry, internal error in intersection");
  345.  
  346.   if (N == size() + P.size())
  347.   { // no intersections between edges of (*this) and P
  348.     // check for inclusion
  349.  
  350.     segment s1 = ptr->seg_list.head();
  351.     segment s2 = P.ptr->seg_list.head();
  352.     point   p1 = s1.start();
  353.     point   p2 = s2.start();
  354.  
  355.     if (P.inside(p1))                     // (*this) is conained in P
  356.       result.append(*this);
  357.     else
  358.       if (inside(p2))                     // P is conained in (*this)
  359.         result.append(P);                   
  360.  
  361.  
  362.     return result;
  363.  
  364.    }
  365.  
  366.   SUB.make_undirected();
  367.  
  368.   edge e;
  369.  
  370.   list(point) PL;
  371.  
  372.   edge_array(bool) marked(SUB,false);
  373.  
  374.   forall_edges(e,SUB) 
  375.   { edge f;
  376.     if (!marked[e]  && SUB.outdeg(target(e))>1) 
  377.       if (polygon_test_edge(SUB,e))
  378.       { // new polygon found
  379.        marked[e] = true;
  380.        PL.append(SUB[source(e)]);
  381.        f = polygon_switch_edge(SUB,e);
  382.        while (f!=e)
  383.        { marked[f] = true;
  384.          PL.append(SUB[source(f)]);
  385.          f = polygon_switch_edge(SUB,f);
  386.         }
  387.        result.append(polygon(PL,false));
  388.        PL.clear();
  389.       }
  390.   }
  391.  
  392.  SUB.make_directed();
  393.  
  394. #endif
  395.  
  396.  return result;
  397.  
  398. }
  399.